from typing import List


class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (1 if i % 2 == 1 else 0)
        return ans


if __name__ == "__main__":
    print(Solution().countBits(2))  # [0,1,1]
    print(Solution().countBits(5))  # [0,1,1,2,1,2]
